package demo14;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 找出所有子集的异或总和再求和
 * https://leetcode.cn/problems/sum-of-all-subset-xor-totals/
 * 优化后
 */
class Solution {
    int path = 0;
    int ret;
    int len;
    public int subsetXORSum(int[] nums) {
        len = nums.length;
        dfs(nums,0);
        return ret;
    }

    private void dfs(int[] nums, int pow) {
        ret += path;

        for(int i = pow; i < len; i++) {
            path ^= nums[i];
            dfs(nums,i+1);
            // 恢复现场
            path ^= nums[i];
        }
    }
}